Skip to main content

110. Balanced Binary Tree

문제

Given a binary tree, determine if it is height-balanced.

예제 입출력

img

Input: root = [3,9,20,null,null,15,7]
Output: true
참고

You can read the full description here.

풀이 1

접근법

  1. 후위 순회를 하면서 리프노드로부터의 거리를 매깁니다.
  2. 좌우 자식 노드의 값이 2 이상 차이나는 경우가 존재하면 False를 리턴합니다.

구현 코드

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
result = True

def postorder(node: Optional[TreeNode]) -> int:
nonlocal result
if node is None:
return -1
left = postorder(node.left)
right = postorder(node.right)

if (abs(left - right) > 1):
result = False

return max(left, right) + 1

postorder(root)

return result

복잡도 분석

  • nn: 노드의 수
  • 시간복잡도: O(n)O(n)

책에 있는 풀이

참고

원본 코드는 여기에서 확인하실 수 있습니다.

풀이 2

접근법

  1. 풀이 1과 유사합니다.

image

구현 코드

class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def check(root):
if not root:
return 0

left = check(root.left)
right = check(root.right)
# 높이 차이가 나는 경우 -1, 이외에는 높이에 따라 1 증가
if left == -1 or \
right == -1 or \
abs(left - right) > 1:
return -1
return max(left, right) + 1

return check(root) != -1

복잡도 분석

  • nn: 노드의 수
  • 시간복잡도: O(n)O(n)